from typing import List
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums.insert(0,1)
        nums.insert(len(nums),1)
        n=len(nums)
        dp=[[0]*len(nums)for m in range(n)]
        for length in range(1,n-1):
            for i in  range(0,n-length-1):
                j=i+length+1
                for k in range(i+1,j):
                    dp[i][j]=max(dp[i][j],dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j])
        return dp[0][n-1]